//
//  20.包含min函数的栈.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/19.
//

import Foundation
/*
 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 函数的时间复杂度都是 O(1).
    push(value)：将元素 value压入栈中
    pop()：弹出栈顶的元素
    top() ：获得栈顶元素
    min() ：获得栈中的最小元素。
 思路：使⽤两个stack，⼀个为数据栈，另⼀个为辅助栈。数据栈⽤于存储所有数据，辅助栈⽤于存储最⼩值。 举个例⼦： ⼊栈的时候：⾸先往空的数据栈⾥压⼊数字3，显然现在3是最⼩值，我们也把最⼩值压⼊辅助栈。接下来往数据栈⾥压⼊数字4。由于4⼤于之前的最⼩ 值，因此我们只要⼊数据栈，不压⼊辅助栈。 出栈的时候：当数据栈和辅助栈的栈顶元素相同的时候，辅助栈的栈顶元素出栈。否则，数据栈的栈顶元素出栈。 获得栈顶元素的时候：直接返回数据栈的栈顶元素。 栈最⼩元素：直接返回辅助栈的栈顶元素。
    
 */
func offer_20() {
    let solution = Solution()
    for i in [3, 4, 1, 2, 1] {
        solution.push(i)
    }
    print(solution.min()!)
    solution.pop()
    print(solution.min()!)
    solution.pop()
    print(solution.min()!)
    solution.pop()
    print(solution.min()!)
}

fileprivate class Solution {
    private var dataStack: Stack<Int> = Stack()
    private var minStack: Stack<Int> = Stack()
    
    func push(_ value: Int) {
        dataStack.push(element: value)
        if minStack.isEmpty() || value <= minStack.peek()! {
            minStack.push(element: value)
        }
    }
    
    @discardableResult
    func pop() -> Int? {
        let data = dataStack.pop()
        if data == minStack.peek() {
            minStack.pop()
        }
        return data
    }
    
    @discardableResult
    func top() -> Int? {
        dataStack.peek()
    }
    
    @discardableResult
    func min() -> Int? {
        minStack.peek()
    }
}


